Error correcting codes are widely used in communications systems. A good reference book for coding in connection with communications systems is R. D. Gitlin, J. F. Hayes and S. B. Weinstein, “Data Communication Principles”, Plenum Press, New York, ISBN 0-306-43777-5 which is incorporated herein by reference. Chapter 3 gives a good description of error correcting and detecting codes and provides references to many other good sources of information in the field. In the field of communications, source information is transmitted or stored into an imperfect medium. A receiver recovers the source information which may be corrupted by errors due to the imperfect medium. Error correcting codes have been developed that add redundancy to transmitted information, enabling correction of errors in the remote receiver.
Block codes are error correcting codes that operate on a fixed size block of digital information. Examples of block codes are Hamming codes and Bose-Chaudhuri-Hocquenghem (BCH) codes. Digital information is transmitted or stored in units or symbols which may contain single digital data bits of information or multiple digital data bits of information. Block codes combine a fixed number of source data symbols and a fixed number of redundant symbols into a coded block containing a fixed number of coded symbols. The coded block of coded symbols is referred to as a “codeword” and the redundant symbols are referred to as “parity symbols”. A block encoder is a device that accepts a fixed number of source data symbols, computes redundant parity symbols relating to the source data symbols and outputs a coded block, or codeword, containing the source data symbols and redundant parity symbols.
Various coding algorithms are available or may be developed for computing the redundant parity symbols. Coding algorithms can be differentiated by the ratio of redundant symbols to source symbols, complexity of encoding, complexity of decoding, number of errors that can be corrected, type of errors that can be corrected, etc. A block decoder is a device that receives the coded block, or codeword, corrects errors in the source symbols, and outputs the corrected source symbols, while discarding the redundant parity symbols.
There is another type of error correcting code known as a “convolutional” error correcting code. The convolutional code operates on a sequence of source symbols to generate an output sequence with additional redundant information. A convolutional encoder is a sequential circuit with memory of previous symbols. Each output symbol is related to all previous symbols, unlike the block encoder, which generates coded blocks, or codewords, that are completely independent of previous blocks or codewords.
Forward error correction (FEC) systems are used in many data communication and storage systems today. These systems “forward” redundant information to the remote receiver to facilitate “error correction.” Systematic codes typically transmit unmodified user source data directly in a block with appended redundant parity information at the end of the block. The encoded block of source data and parity information is commonly known as a “codeword.” A decoder in the remote receiver utilizes the redundant information to correct errors that may have occurred during transmission.
FEC codes are selected for properties that benefit specific applications. Hamming codes and Bose-Chaudhuri-Hocquenghem (BCH) codes are two of many examples. The popular Reed-Solomon (RS) codes are a subclass of BCH codes. Many FEC systems implement concatenated codes, such as a RS block code concatenated with a convolutional trellis code. Block codes, such as the Hamming, BCH, and RS codes, can correct multiple errors that may occur in a block of data. Most codes are designed to correct random errors, although some codes are designed to correct burst errors that occur on sequential symbols. Burst error events may cause a large number of errors in a single block. In burst error environments, the FEC system may include an interleaved block code concatenated with a distributed trellis encoder. The FEC block codes encode k source data symbols into a fixed block or codeword of n symbols containing p redundant parity check symbols where p=n−k. RS codes can correct up to p/2 random symbol errors in a block of n symbols. A burst of errors in excess of the error correcting capacity of the code (p/2) will cause the FEC decoder to fail, resulting in errors in the decoded block. Interleaving methods are used to interleave the blocks dispersing the symbols of each encoded block over a large number of blocks. The interleaved blocks are transmitted into or stored in a communication medium susceptible to burst error events. A deinterleaver in the receiver reassembles the encoded blocks, while beneficially dispersing the burst errors among many blocks. Each block then has fewer errors that can be reliably corrected by the code.
Interleavers, such as a convolutional interleaver, are used in the art to disperse burst errors. A convolutional interleaver may pass coded symbols through B sections or branches of increasing delay. Each section has delay increasing in steps of M symbols. The first section has a delay of zero and the last section has a delay of M*(B−1) symbols. Thus, adjacent symbols from any codeword are separated by B symbol periods at the interleaver output. This convolutional interleaver can protect against error burst durations of B symbol periods. For a block or codeword size of n symbols and M*B greater than or equal to n, a burst duration less than M*B symbol periods will result in no more than M errors in the interleaved block. The deinterleaver operates in the reverse order passing the first received symbol through a delay section of M*(B−1) symbols and the next received symbols through sections having M fewer delayed symbols per section. The final received symbol is passed through a section with no delay. The total delay of combined interleaver and deinterleaver is then M*(B−1) symbol periods for all symbols.
Conventional interleaving methods have undesirable side effects. Conventional interleavers delay the data prior to transmission and scramble the original order of the source data. The reordered source symbols yield unrecognizable data at remote receivers unless they are deinterleaved. A deinterleaver is required in the receiver to reassemble the data in the correct order for decoding. The deinterleaver adds undesirable additional delay and typically must be synchronized with the remote interleaver. The codeword symbols are spread out in the channel over M*B*(B−1) symbol periods. The final decoding of the full codeword is delayed by M*B*(B−1)+n−1 symbol periods. The conventional interleavers and deinterleavers add complexity to equipment and usually require significant additional memory.
There is a need in the industry for better systems and methods for correcting burst errors. The inventor has discovered a new coding methodology that addresses, among other things, the correction of burst errors.